package arrAndstr;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/*
    56. 合并区间
 */
public class T56 {
    public static void main(String[] args) {
        int[][] intervals = new int[][]{
                {2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 10},
        };
        int[][] mergeArray = merge(intervals);
        for (int[] interval : mergeArray) {
            System.out.println(interval[0] + "-" + interval[1] + "  ");
        }
    }

    public static int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if (len == 1) return intervals;
        // 根据第一个元素进行排序
//        sortArray(intervals);
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        // 进行判断
        List<int[]> list = new ArrayList<>();
        // 直接修改list -> 因为每次只修改最后一个元素
        list.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int lastIndex = list.size() - 1;
            if (list.get(lastIndex)[1] >= intervals[i][0]
                    && intervals[i][1] > list.get(lastIndex)[1]) {
                list.set(lastIndex, new int[]{list.get(lastIndex)[0], intervals[i][1]});
            } else if (intervals[i][1] > list.get(lastIndex)[1]){
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[1][2]);
    }

    public static void sortArray(int[][] array) {   // 根据第一个元素排序
        for (int i = 0; i < array.length; i++) {
            for (int j = 1; j < array.length - i; j++) {
                if (array[j][0] < array[j - 1][0]) {
                    int[] temp = new int[]{array[j - 1][0], array[j - 1][1]};

                    array[j - 1][0] = array[j][0];
                    array[j - 1][1] = array[j][1];

                    array[j][0] = temp[0];
                    array[j][1] = temp[1];
                }
            }
        }
    }
}
